package leetcode100;

import java.util.Scanner;

/**
 * @author shkstart
 * @create 2022-12-26-23:11
 */
public class Meme25_1 {
    public static void main(String[] args) {
        int[]num =new int[10001];
        num[1] =1;
        num[2]=2;
        for (int i = 3; i < 1001; i++) {
            num[i] =(num[i-1]+num[i-2])%10000;
        }
        Scanner scanner = new Scanner(System.in);
        StringBuilder sb= new StringBuilder();
        while(scanner.hasNext()){
            int n =scanner.nextInt();
            for (int i = 0; i < n; i++) {
                int xi =scanner.nextInt();
                sb.append(String.format("%04d", num[xi]));
            }
            System.out.println(sb);
        }
    }
}
